#include <unordered_map>
class Solution {
public:
    vector<int> getPath(TreeNode* root, int target) {
        vector<int> path;
        TreeNode* node = root;
        while (node->val != target) {
            path.push_back(node->val);
            if (node->val < target) {
                node = node->right;
            } else {
                node = node->left;
            }
        }
        path.push_back(node->val);
        return path;
    }

    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        int res = root->val;
        vector<int> pathp = getPath(root, p);
        vector<int> pathq = getPath(root, q);
        for (int i = 1; i < min(pathp.size(), pathq.size()); i++) {
            if (pathp[i] == pathq[i]) {
                res = pathp[i];
            } 
            else break;
        }
        return res;
    }
}; 